package impl.search;

/**
 * Created by IntelliJ IDEA.
 * User: Tomi
 * Date: 03/11/2011
 * Time: 20:27:35
 * To change this template use File | Settings | File Templates.
 */
public class InterpolatedOrderedArray<K, V> extends AbstractOrderedArray<K, V> {
    public InterpolatedOrderedArray() {
        super();
    }
    public int search(Object key, int i, int f) {
        int k = Math.abs(key.hashCode());
        if((f-i)>10){
            int ki = Math.abs((A.get(i).getKey()).hashCode());
            int kf = Math.abs((A.get(f).getKey()).hashCode());
            double d = ((double)(k - ki)/(double)(kf - ki))*(f - i - 1);
            int id = (int)d;
            while(id<i || id>f){
                if(id<i){
                    id = id*2;
                }
                if(id>f){
                    id = id/2;
                }
            }
            if(k<ki){
                return search(key, i, id-1);
            }else if(k>ki){
                return search(key, id+1, f);
            }else{
                return id;
            }
        }else{
            for(int j=i; j<f; j++){
                if(k == A.get(j).getKey().hashCode()){
                    return j;
                }
            }
        }
        return -1;
    }
}